#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#include "sqstack.h"
#include "queue.h"

void Init(BinaryTree *bt, char ref)
{
	bt->root = NULL;
	bt->refvalue = ref;
}

void Create1(BinaryTree *bt, char **strp)
{
	Create1_(bt, &bt->root, strp);
}

void Create1_(BinaryTree *bt, BinaryTreeNode **rootp, char **strp)
{
	if (**strp == bt->refvalue) //'#'
	{
		*rootp = NULL;
		return;
	}

	BinaryTreeNode *node = malloc(sizeof(BinaryTreeNode));
	if (node == NULL)
	{
		perror("malloc()");
		exit(EXIT_FAILURE);
	}

	node->data = **strp;
	*rootp = node; //修改变量的值,函数参数为一级指针;修改指针的值,函数参数为二级指针。

	++(*strp);				  //修改字符串起始位置为左子树根
	Create1_(bt, &(*rootp)->leftchild, strp); //递归创建左子树
	++(*strp);
	Create1_(bt, &(*rootp)->rightchild, strp); //递归创建右子树
}

void Create2(BinaryTree *bt, char **strp)
{
	bt->root = Create2_(bt, strp);
}

BinaryTreeNode *Create2_(BinaryTree *bt, char **strp)
{
	char *str = *strp;

	if (*str == bt->refvalue)
		return NULL;

	BinaryTreeNode *node = malloc(sizeof(BinaryTreeNode));
	if (node == NULL)
	{
		perror("malloc()");
		exit(EXIT_FAILURE);
	}
	node->data = *str;
	++(*strp);
	node->leftchild = Create2_(bt, strp);
	++(*strp);
	node->rightchild = Create2_(bt, strp);
	return node;
}

void PreOrder(BinaryTree *tree)
{
	if (tree->root != NULL)
		PreOrder_(tree->root);
	printf("\n");
}

void PreOrder_(BinaryTreeNode *root)
{
	printf("%c ", root->data);
	if (root->leftchild != NULL) //前，中序遍历的这种判断方式感觉比后序遍历的方式递归的层数更少
		PreOrder_(root->leftchild);
	if (root->rightchild != NULL)
		PreOrder_(root->rightchild);
}

void InOrder(BinaryTree *tree)
{
	if (tree->root != NULL)
		InOrder_(tree->root);
	printf("\n");
}

void InOrder_(BinaryTreeNode *root)
{
	if (root->leftchild != NULL)
		InOrder_(root->leftchild);
	printf("%c ", root->data);
	if (root->rightchild != NULL)
		InOrder_(root->rightchild);
}

void PostOrder(BinaryTree *tree)
{
	PostOrder_(tree->root);
	printf("\n");
}

void PostOrder_(BinaryTreeNode *root)
{
	if (root != NULL)
	{
		PostOrder_(root->leftchild);
		PostOrder_(root->rightchild);
		printf("%c ", root->data);
	}
}

void LevelOrder(BinaryTreeNode *root)
{
	if (root == NULL)
		return;

	Queue q;
	BinaryTreeNode *v = NULL;

	InitQueue(&q);
	EnQueue(&q, root);
	while (!QueueIsEmpty(&q)) //队列非空
	{
		GetHead(&q, &v); //访问该结点
		printf("%c ", v->data);
		DeQueue(&q);		  //该结点出队
		if (v->leftchild != NULL) //结点左孩子入队
			EnQueue(&q, v->leftchild);
		if (v->rightchild != NULL) //结点右孩子入队
			EnQueue(&q, v->rightchild);
	}
	Destory(&q);
	printf("\n");
}

int Size(BinaryTree *tree)
{
	return Size_(tree->root);
}

int Size_(BinaryTreeNode *node)
{
	if (node == NULL)
		return 0;
	return Size_(node->leftchild) + Size_(node->rightchild) + 1;
}

int Height(BinaryTreeNode *node)
{
	if (node == NULL)
		return 0;
	int left_height = Height(node->leftchild);
	int right_height = Height(node->rightchild);
	return (left_height > right_height ? left_height : right_height) + 1;
}

BinaryTreeNode *Search(BinaryTreeNode *node, char key)
{
	if (node == NULL)
		return NULL;
	if (node->data == key)
		return node;
	BinaryTreeNode *p = Search(node->leftchild, key); //在左树中寻找
	if (p != NULL)
		return p; //关键，左树中找到就直接返回,不需要再查找
	else
		return Search(node->rightchild, key);
}

BinaryTreeNode *Parent(BinaryTreeNode *p, BinaryTreeNode *node)
{
	if (p == NULL || node == NULL)
		return NULL; //这两种情况都不可能有父节点
	if (p->leftchild == node || p->rightchild == node)
		return p;
	BinaryTreeNode *q = Parent(p->leftchild, node);
	if (q != NULL)
		return q;
	else
		return Parent(p->rightchild, node);
}

// BinaryTreeNode *LeftChild(BinaryTreeNode *p)
//{
//	if (p != NULL)
//		return p->leftchild;
//	return NULL;
// }
//
// BinaryTreeNode *RightChild(BinaryTreeNode *p)
//{
//	if (p != NULL)
//		return p->rightchild;
//	return NULL;
// }

// int Empty(BinaryTree *tree)
//{
//	if (tree != NULL)
//		return tree->root == NULL;
//	return 0;
// }

void Copy(BinaryTreeNode *p, BinaryTreeNode **q)
{
#if 1
	if (p == NULL)
		*q = NULL;
	else
	{
		BinaryTreeNode *new = malloc(sizeof(BinaryTreeNode));
		if (new == NULL)
		{
			perror("malloc()");
			exit(EXIT_FAILURE);
		}
		new->data = p->data;
		*q = new;
		Copy(p->leftchild, &new->leftchild);
		Copy(p->rightchild, &new->rightchild);
	}
#endif

	//把Copy函数写在外面的写法,这时如果p为空则不能取leftchild，所以在p为空时需直接返回
#if 0
	if (p == NULL)
	{
		*q == NULL;
		return;
	}
	else
	{
		*q = malloc(sizeof(BinaryTreeNode));
		if (*q == NULL)
			exit(1);
		(*q)->data = p->data;
	}
	Copy(p->leftchild, &(*q)->leftchild);
	Copy(p->rightchild, &(*q)->rightchild);
#endif
}

void Clear(BinaryTreeNode **node)
{
	BinaryTreeNode *current = *node;
	if (current != NULL)
	{
		Clear(&current->leftchild);
		Clear(&current->leftchild);
		free(current);
		*node = NULL;
		// current = NULL;     错误写法
	}
}

//和层次遍历有点像，不过一个用的是队列，一个用的是栈
int _PreOrder(BinaryTreeNode *node)
{
	if (node == NULL)
		return -1;

	sqstack *stack;
	BinaryTreeNode *current;
	int err;

	stack = stack_create();
	if (stack == NULL)
	{
		fprintf(stderr, "stack_create failed!\n");
		exit(EXIT_FAILURE);
	}
	err = stack_push(stack, &node);
	if (err == -1)
	{
		fprintf(stderr, "stack_push failed!\n");
		exit(EXIT_FAILURE);
	}
	while (!stack_isempty(stack))
	{
		stack_pop(stack, &current); //栈顶元素出栈访问
		printf("%c ", current->data);
		if (current->rightchild != NULL)
			stack_push(stack, &current->rightchild); //右孩子入栈
		if (current->leftchild != NULL)
			stack_push(stack, &current->leftchild); //左孩子入栈
	}
	printf("\n");

	return 0;
}

int _PreOrder2(BinaryTreeNode *node)
{
	if (node == NULL)
		return -1;

	sqstack *stack = stack_create();
	BinaryTreeNode *current = node;

	if (stack == NULL)
	{
		fprintf(stderr, "stack_create failed!\n");
		exit(EXIT_FAILURE);
	}
	while (current || !stack_isempty(stack))
	{
		if (current)
		{
			printf("%c ", current->data);
			stack_push(stack, &current);
			current = current->leftchild;
		}
		else
		{
			stack_pop(stack, &current);
			current = current->rightchild;
		}
	}

	printf("\n");
	return 0;
}

int _InOrder(BinaryTreeNode *node)
{
	if(node == NULL)
		return -1;

	sqstack *stack;
	BinaryTreeNode *current = node;

	stack = stack_create();
	if (stack == NULL)
	{

		fprintf(stderr, "stack_create failed!\n");
		exit(EXIT_FAILURE);
	}

	while (current || !stack_isempty(stack))
	{
		if (current)      //一路向左
		{
			stack_push(stack, &current);  //当前结点入栈
			current = current->leftchild;  //左孩子不空，一直向左走
		}
		else
		{
			stack_pop(stack, &current);   //栈顶元素出栈访问
			printf("%c ", current->data);
			current = current->rightchild;   //向右子树走
		}
	}

	printf("\n");
	return 0;
}

void _PostOrder(BinaryTreeNode *node)
{
}